Faster exponential-time algorithms in graphs of bounded average degree

摘要

We present a number of exponential-time algorithms for problems in sparse matrices and graphs of bounded average degree. First, we obtain a simple algorithm that computes a permanent of an n×n matrix over an arbitrary commutative ring with at most dn non-zero entries using O⋆(2(1−1/(3.55d))n) time and ring operations, 1 improving and simplifying the recent result of Izumi and Wadayama [FOCS 2012].\ud\udSecond, we present a simple algorithm for counting perfect matchings in an n -vertex graph in O⋆(2n/2) time and polynomial space; our algorithm matches the complexity bounds of the algorithm of Björklund [SODA 2012], but relies on inclusion–exclusion principle instead of algebraic transformations.\ud\udThird, we show a combinatorial lemma that bounds the number of “Hamiltonian-like” structures in a graph of bounded average degree. Using this result, we show that\ud\ud1. a minimum weight Hamiltonian cycle in an n-vertex graph with average degree bounded by d can be found in O⋆(2(1−εd)n) time and exponential space for a constant εd depending only on d;\ud2. the number of perfect matchings in an n-vertex graph with average degree bounded by d can be computed in View the MathML source time and exponential space, for a constant View the MathML source depending only on d.\ud\udThe algorithm for minimum weight Hamiltonian cycle generalizes the recent results of Björklund et al. [TALG 2012] on graphs of bounded degree.